package org.example.myleet.p846;

import java.util.*;

public class Solution {
    /**
     * 思路：贪心+排序+哈希表
     * 贪心：hand一定要是groupSize的倍数才满足题目要求，hand中未分组的最小x一定要能够被分到某一组中，换言之[x, x + groupSize - 1]中的数字都必须存在
     * 排序：从最小未分组的x开始找
     * 哈希表：题目的hand中的元素可能非常大，需要用哈希表记录元素的出现次数，每次执行分组操作都减去相应都元素出现次数
     */
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n % groupSize != 0) {
            return false;
        }
        //排序
        Arrays.sort(hand);
        Map<Integer, Integer> buckets = new HashMap<>();
        for (int h : hand) {
            //记录出现次数
            int count = buckets.getOrDefault(h, 0);
            buckets.put(h, count + 1);
        }
        int i = 0;
        while (i < n) {
            int num = hand[i], numCount = buckets.getOrDefault(num, 0);
            if (numCount == 0) {
                //此元素已经完成分组，略过
                ++i;
                continue;
            }
            buckets.put(num, numCount - 1);
            for (int j = 1; j < groupSize; ++j) {
                ++num;
                numCount = buckets.getOrDefault(num, 0);
                if (numCount == 0) {
                    //分组中存在缺少的元素，不能形成顺子
                    return false;
                }
                --numCount;
                buckets.put(num, numCount);
            }
            ++i;
        }
        return true;
    }
}
